package com.backpack;

/**
 * 买卖股票的最佳时机含冷冻期
 * 输入: prices = [1,2,3,0,2]
 * 输出: 3
 * 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
 */
public class BestTimetoBuyandSellStockwithCooldown0116_309 {
    public int maxProfit(int[] prices) {
        //动态规划
        //dp含义
        //  四个状态：dp[i][0] 持有股票 的手头现金最大值
        //          dp[i][1] 卖出股票 的手头现金最大值
        //          dp[i][2] 冷冻期，不能操作，手头现金最大值
        //          dp[i][3] 保持"无股票"状态（已经之前卖出），手头现金最大值。
        int[][] dp = new int[prices.length][4];

        //初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;

        //遍历公式
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][2]-prices[i],dp[i-1][3]-prices[i]));
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = dp[i-1][1];
            dp[i][3] = Math.max(dp[i-1][2],dp[i-1][3]);
        }
        return Math.max(dp[prices.length-1][3], Math.max(dp[prices.length-1][2],dp[prices.length-1][1]));
    }
}
